#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
template<typename T>
class splay
{
private:
    static const int MAXN = 200000;
    T value[MAXN];
    int key[MAXN], ch[MAXN][2], fa[MAXN], sz[MAXN],tot,root;
    int idx[MAXN];
    void pushup(int x);
    // void pushdown(int x);
    void rotate(int x,int &k);
    void _splay(int x,int &k);
	void _insert(int &x, int pr, int k, T v);
public:
	splay(){
		ch[0][0] = ch[0][1] = 0;
		fa[0] = 0;
		sz[0] = 0;
		tot = 0;
		root = 0;
	}
	void insert(int key, T value);
	void remove(int key);
	// 得到key的rank
	int getRank(int key);
	// 得到rank为r的value 与 key
	void getByRank(int r, int& k, T& v);
};
template<typename T>
void splay<T>::pushup(int x){
    int lson = ch[x][0];
    int rson = ch[x][1];
    sz[x] = sz[lson] + sz[rson] + 1;
}

template<typename T>
void splay<T>::rotate(int x,int &k){
	int y=fa[x],z=fa[y],l,r;
	if(ch[y][0]==x)l=0;else l=1;r=l^1;
	if(y==k)k=x;
	else{if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
	fa[y]=x;fa[x]=z;fa[ch[x][r]]=y;
	ch[y][l]=ch[x][r];ch[x][r]=y;
	pushup(y);pushup(x);
}

template<typename T>
void splay<T>::_splay(int x,int &k){
	while(x!=k){
		// cout << x << " " << k << endl;
		int y=fa[x],z=fa[y];
		if(y!=k){
			if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);
			else rotate(y,k);
		}rotate(x,k);
	}
}

template<typename T>
void splay<T>::_insert(int &x, int pr, int k, T v){
	// cout << x << endl;
	if(!x){
		x=++tot;
		idx[k] = tot;
		sz[x]=1;
		fa[x]=pr;
		key[x]=k;
		value[x]=v;
		_splay(x, root);
		return;
	}
	if(v > value[x]){
		_insert(ch[x][1], x, k, v);
	}else{
		_insert(ch[x][0], x, k, v);
	}	
}

template<typename T>
void splay<T>::insert(int k, T v){
	_insert(root, 0, k, v);
}

template<typename T>
void splay<T>::remove(int key){
	_splay(idx[key], root);
	if(ch[root][1] == 0){
		root = ch[root][0];
		fa[root] = 0;
		return ;
	}
	if(ch[root][0] == 0){
		root = ch[root][1];
		fa[root] = 0;
		return ;
	}
	int pr = ch[root][1];
	while(ch[pr][1]!=0)pr=ch[pr][1];
	int af = ch[root][0];
	while(ch[af][0]!=0)af=ch[af][0];
	// cout << "da\n" << pr << " " << af << endl;
	_splay(pr, root);
	// cout << af << " " << root;
	_splay(af, ch[root][1]);//cout << "d3a\n";
	fa[ch[ch[root][1]][0]] = 0;
	ch[ch[root][1]][0] = 0;
	pushup(ch[root][1]);pushup(root);
}

template<typename T>
int splay<T>::getRank(int k){
	int i = idx[k];
	_splay(i, root);
	return sz[ch[root][0]] + 1;
}

template<typename T>
void splay<T>::getByRank(int r, int &k, T& v){
	int cur = root;
	while(r){
		// cout <<"abab: "<< cur <<" "<<ch[cur][0] << " " << ch[cur][1]<<" " << r<< endl;
		// cout << sz[ch[cur][0]] << " " << sz[ch[cur][1]] << endl;
		// exit(0);
		if(sz[ch[cur][0]]+1 == r){
			break;
		}else if(sz[ch[cur][0]]+1<r){
			r -= sz[ch[cur][0]] + 1;
			cur = ch[cur][1];
		}else if(sz[ch[cur][0]] >= r){
			cur = ch[cur][0];
		}else{
			exit(-1);
			// cout << "wrong!\n";
		}
	}
	_splay(cur, root);
	v = value[root];
	k = key[root];
}